#ifndef LEETCODE_CN_CPP_PROBLEMS_146_H
#define LEETCODE_CN_CPP_PROBLEMS_146_H

#include <list>
#include <unordered_map>

using namespace std;

namespace problem_146
{

class LRUCache
{
private:
    int capacity;
    list<pair<int, int>> lru;
    unordered_map<int, list<pair<int, int>>::iterator> cache;

public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key)
    {
        auto iter = cache.find(key);
        if (iter == cache.end())
            return -1;
        int value = iter->second->second;
        lru.erase(iter->second);
        lru.emplace_front(key, value);
        iter->second = lru.begin();
        return value;
    }

    void put(int key, int value)
    {
        if (capacity <= 0)
            return;
        auto iter = cache.find(key);
        if (iter != cache.end())
        {
            lru.erase(iter->second);
            lru.emplace_front(key, value);
            iter->second = lru.begin();
            return;
        }
        if (lru.size() >= capacity)
        {
            cache.erase(lru.back().first);
            lru.pop_back();
        }
        lru.emplace_front(key, value);
        cache.emplace(key, lru.begin());
    }
};

} // namespace problem_146

#endif //LEETCODE_CN_CPP_PROBLEMS_146_H
